package newcoder_exp.justPractise;

// import java.util.Arrays;

// import org.junit.Test;
import java.util.*;
import org.junit.*;

/* 
求next数组并应用
*/
public class NC149 {
    public class Solution {

        public int kmp (String S, String T) {
            int res = 0;
            String s = T;
            int s1, s2;
            for (int i = 0; i < T.length(); i++) {
                String str = s.substring(i);
                if (str.length() < T.length()) break;
                int[] next = getNext(str);
                s1 = 0; 
                s2 = 0;
                while (s1 < str.length() && s2 < T.length()) {
                    if (s2 >= 0 && str.charAt(s1) == T.charAt(s2)) {
                        s1++;
                        s2++;
                    } else {
                        if (s2 != -1) {
                            s1++;
                        } else {
                            s2 = next[s2];
                        }
                    }
                }
                if (s2 == T.length()) res++;
            }
            return res;
        }
        
        public int[] getNext(String s) {
            int len = s.length();
            int[] next = new int[len];
            next[0] = -1;
            next[1] = 0;
            //若next[i - 1]已经得到=m，则可知s[0~m-1] == s[i - m - 1~i - 2]，即头尾的m个字符相等
            //对于新出现的这个位置s[i-1],只要他能够等于s[m],就可以说明当前最长的相同串为m + 1;
            //若是不相等，再查看m位置的next[m]，继续查看下个较小的前后缀的后位是否与s[i-1]相同
            int n, cur, idx = 2;
            //没有相同前后缀了
            while (idx < len) {
                cur = idx - 1;
                if (s.charAt(idx - 1) == s.charAt(n = next[cur])) {
                    next[idx++] = n + 1;
                } else if (n > 0) { //仍然有前后缀探查
                    cur = n;
                } else {
                    next[idx++] = 0;
                }
            }
            return next;
        }
    }

    @Test
    public void test() {
        String s = "ababc";
        Solution so = new Solution();
        int[] res = so.getNext(s);
        int r = so.kmp("ababab","abababab");
        System.out.println(r);
        System.out.println(Arrays.toString(res));
    }
}
